{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Balanced Parentheses Check - SOLUTION\n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Given a string of opening and closing parentheses, check whether it’s balanced. We have 3 types of parentheses: round brackets: (), square brackets: [], and curly brackets: {}. Assume that the string doesn’t contain any other character than these, no spaces words or numbers. As a reminder, balanced parentheses require every opening parenthesis to be closed in the reverse order opened. For example ‘([])’ is balanced but ‘([)]’ is not. \n",
    "\n",
    "\n",
    "You can assume the input string has no spaces.\n",
    "\n",
    "## Solution\n",
    "\n",
    "This is a very common interview question and is one of the main ways to check your knowledge of using Stacks! We will start our solution logic as such:\n",
    "\n",
    "First we will scan the string from left to right, and every time we see an opening parenthesis we push it to a stack, because we want the last opening parenthesis to be closed first. (Remember the FILO structure of a stack!)\n",
    "\n",
    "Then, when we see a closing parenthesis we check whether the last opened one is the corresponding closing match, by popping an element from the stack. If it’s a valid match, then we proceed forward, if not return false. \n",
    "\n",
    "Or if the stack is empty we also return false, because there’s no opening parenthesis associated with this closing one. In the end, we also check whether the stack is empty. If so, we return true, otherwise return false because there were some opened parenthesis that were not closed. \n",
    "\n",
    "Here's an example solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def balance_check(s):\n",
    "    \n",
    "    # Check is even number of brackets\n",
    "    if len(s)%2 != 0:\n",
    "        return False\n",
    "    \n",
    "    # Set of opening brackets\n",
    "    opening = set('([{') \n",
    "    \n",
    "    # Matching Pairs\n",
    "    matches = set([ ('(',')'), ('[',']'), ('{','}') ]) \n",
    "    \n",
    "    # Use a list as a \"Stack\"\n",
    "    stack = []\n",
    "    \n",
    "    # Check every parenthesis in string\n",
    "    for paren in s:\n",
    "        \n",
    "        # If its an opening, append it to list\n",
    "        if paren in opening:\n",
    "            stack.append(paren)\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            # Check that there are parentheses in Stack\n",
    "            if len(stack) == 0:\n",
    "                return False\n",
    "            \n",
    "            # Check the last open parenthesis\n",
    "            last_open = stack.pop()\n",
    "            \n",
    "            # Check if it has a closing match\n",
    "            if (last_open,paren) not in matches:\n",
    "                return False\n",
    "            \n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balance_check('[]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balance_check('[](){([[[]]])}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balance_check('()(){]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestBalanceCheck(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        assert_equal(sol('[](){([[[]]])}('),False)\n",
    "        assert_equal(sol('[{{{(())}}}]((()))'),True)\n",
    "        assert_equal(sol('[[[]])]'),False)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "# Run Tests\n",
    "\n",
    "t = TestBalanceCheck()\n",
    "t.test(balance_check)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
